/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class MaximumSumof3NonOverlappingSubarrays {
	public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
		int n = nums.length;
		int[] W = new int[n - k + 1];
		int s = 0;
		for (int i = 0; i < k; i++) {
			s += nums[i];
		}
		for (int i = k; i < n; i++) {
			W[i - k] = s;
			s -= nums[i - k];
			s += nums[i];
		}
		W[n - k] = s;
		for (int i : W) {
			System.out.println(i);
		}

		int left[] = new int[W.length];
		int tmp = 0;
		int index = 0;
		for (int i = 0; i < left.length; i++) {
			if (W[i] > W[index]) {
				index = i;
			}
			left[i] = index;
		}
		int right[] = new int[W.length];
		index = right.length - 1;
		for (int i = right.length - 1; i >= 0; i--) {
			if (W[i] >= W[index]) {
				index = i;
			}
			right[i] = index;
		}

		int max = 0;
		int res[] = new int[3];
		for (int j = k; j <= n - 2 * k; j++) {
			int i = left[j - k], j2 = right[j + k];
			tmp = W[i] + W[j] + W[j2];
			if (tmp > max) {
				max = tmp;
				res[0] = i;
				res[1] = j;
				res[2] = j2;
			}
		}
		return res;
	}

	public int[] maxSumOfThreeSubarrays2(int[] nums, int k) {
		int n = nums.length;
		int[] sum = new int[n];
		int res[] = new int[3];
		for (int i = 0; i < n; i++) {
			sum[i] = (i == 0 ? 0 : sum[i - 1]) + nums[i];
		}
		int max = 0;
		for (int i = 0; i <= n - 3 * k; i++) {
			int s1 = sum[i + k - 1] - (i == 0 ? 0 : sum[i - 1]);
			for (int j = i + k; j <= n - 2 * k; j++) {
				int s2 = sum[j + k - 1] - sum[j - 1];
				for (int j2 = j + k; j2 <= n - k; j2++) {
					int s = s1 + s2 + sum[j2 + k - 1] - sum[j2 - 1];
					if (s > max) {
						max = s;
						res[0] = i;
						res[1] = j;
						res[2] = j2;
					}
				}
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int nums[] = { 7, 13, 20, 19, 19, 2, 10, 1, 1, 19 };
		int k = 3;
		int res[] = new MaximumSumof3NonOverlappingSubarrays().maxSumOfThreeSubarrays(nums, k);
		System.out.println(res[0]);
		System.out.println(res[1]);
		System.out.println(res[2]);
	}

}
